package code.oldCode.classic150;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author cuihaoran
 * @date 2024/12/17
 */
public class Classic150_matrix {
    /* 36. 有效的数独 */
    public boolean isValidSudoku(char[][] board) {
        // 检查每一行是否符合要求
        for (int i = 0; i < 9; i++) {
            HashSet<Character> hashSet = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && hashSet.contains(board[i][j])) {
                    return false;
                }
                hashSet.add(board[i][j]);
            }
        }
        // 检查每一列是否符合要求
        for (int i = 0; i < 9; i++) {
            HashSet<Character> hashSet = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[j][i] != '.' && hashSet.contains(board[j][i])) {
                    return false;
                }
                hashSet.add(board[j][i]);
            }
        }
        // 检查每一小块是否符合要求
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                HashSet<Character> hashSet = new HashSet<>();
                int i_begin = i * 3;
                int j_begin = j * 3;
                for (int k = i_begin; k < i_begin + 3; k++) {
                    for (int l = j_begin; l < j_begin + 3; l++) {
                        if (board[k][l] != '.' && hashSet.contains(board[k][l])) {
                            return false;
                        }
                        hashSet.add(board[k][l]);
                    }
                }
            }
        }
        return true;
    }

    /* 54. 螺旋矩阵 */
    public List<Integer> spiralOrder(int[][] matrix) {
        int row = matrix.length;
        int column = matrix[0].length;
        boolean[][] isVisited = new boolean[row][column];
        int visit = 0;
        List<Integer> list = new ArrayList<>();
        // → ↓ ← ↑
        int[] rowPos = new int[]{0, 1, 0, -1};
        int[] columnPos = new int[]{1, 0, -1, 0};
        int nxt = 0;
        int i = 0, j = 0;
        while (visit < row * column) {
            list.add(matrix[i][j]);
            visit++;
            isVisited[i][j] = true;
            // 找下一个位置
            int tempI = i + rowPos[nxt];
            int tempJ = j + columnPos[nxt];
            if (0 <= tempI && tempI < row && 0 <= tempJ && tempJ < column && !isVisited[tempI][tempJ]) {
                i = tempI;
                j = tempJ;
            } else {
                nxt = (nxt + 1) % 4;
                i = i + rowPos[nxt];
                j = j + columnPos[nxt];
            }
        }
        return list;
    }

    /* 48. 旋转图像 */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int times = (n + 1) / 2;
        for (int i = 0; i < times; i++) {
            int len = n - 2 * i - 1;
            for (int j = i; j < i + len; j++) {
                int temp = matrix[i][j];
                int sub = j - i;
                matrix[i][j] = matrix[i + len - sub][i];
                matrix[i + len - sub][i] = matrix[i + len][i + len - sub];
                matrix[i + len][i + len - sub] = matrix[j][i + len];
                matrix[j][i + len] = temp;
            }
        }
    }

    /* 73. 矩阵置零 */
    public void setZeroes(int[][] matrix) {
        Set<Integer> row = new HashSet<>();
        Set<Integer> column = new HashSet<>();
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    column.add(j);
                }
            }
        }
        for (int i = 0; i < rowLen; i++) {
            if (row.contains(i)) {
                for (int j = 0; j < colLen; j++) {
                    matrix[i][j] = 0;
                }
                continue;
            }
            for (int j = 0; j < colLen; j++) {
                if (column.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /* 289. 生命游戏 */
    public void gameOfLife(int[][] board) {
        int row = board.length;
        int col = board[0].length;
        int[] direct = new int[]{-1, 0, 1};
        // 0 死-死
        // 2 死-活
        // 1 活-活
        // 3 活-死
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int aroundAlive = 0;
                if (board[i][j] == 1)
                    aroundAlive--;
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        int posI = i + direct[k];
                        int posJ = j + direct[l];
                        if (0 <= posI && posI < row && 0 <= posJ && posJ < col && (board[posI][posJ] == 1 || board[posI][posJ] == 3))
                            aroundAlive++;
                    }
                }
                if (board[i][j] == 1) {
                    if (aroundAlive < 2 || aroundAlive > 3)
                        board[i][j] = 3;
                } else if (board[i][j] == 0) {
                    if (aroundAlive == 3)
                        board[i][j] = 2;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 2)
                    board[i][j] = 1;
                else if (board[i][j] == 3)
                    board[i][j] = 0;
            }
        }
    }
}
